package tree

//给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。
//
//假定 BST 有如下定义：
//
//结点左子树中所含结点的值小于等于当前结点的值
//结点右子树中所含结点的值大于等于当前结点的值
//左子树和右子树都是二叉搜索树
//提示：如果众数超过1个，不需考虑输出顺序

//FindMode 直接利用中序遍历:基于二叉搜索树中序遍历的性质：一棵二叉搜索树的中序遍历序列是一个非递减的有序序列,重复出现的数字一定是一个连续出现的段内
//复杂度：
//时间复杂度：O(n) 即遍历这棵树的复杂度。
//空间复杂度：O(n) 即递归的栈空间的空间代价。
func FindMode(root *Node) (answer []int) {
	var base, count, maxCount int // base 当前的数字，count 当前数字重复的次数 maxCount 已扫描过的的数当中出现最多的那个数字的出现次数

	//扫描更新函数
	update := func(x int) {
		if base == x { // 扫描的新元素和base相等，将出现次数+1
			count++
		} else {
			base, count = x, 1 //新的扫描元素
		}

		if count == maxCount { //当前次数等于众数
			answer = append(answer, base) // 加入结果数组
		} else if count > maxCount { //当前数字出现的次数大于当前众数出现的次数，进行更新
			maxCount = count
			answer = []int{base}
		}
	}

	var dfs func(*Node)
	dfs = func(node *Node) {
		if node == nil {
			return
		}
		dfs(node.Left)
		update(node.Val) //更改众数
		dfs(node.Right)
	}
	dfs(root)
	return
}

//Morris 中序遍历
//接着上面的思路，我们用 Morris 中序遍历的方法把中序遍历的空间复杂度优化到 O(1)。 我们在中序遍历的时候，一定先遍历左子树，然后遍历当前节点，最后遍历右子树。在常规方法中，我们用递归回溯或者是栈来保证遍历完左子树可以再回到当前节点，但这需要我们付出额外的空间代价。我们需要用一种巧妙地方法可以在 O(1)的空间下，遍历完左子树可以再回到当前节点。
//我们希望当前的节点在遍历完当前点的前驱之后被遍历，我们可以考虑修改它的前驱节点的 right 指针。当前节点的前驱节点的 right 指针可能本来就指向当前节点（前驱是当前节点的父节点），也可能是当前节点左子树最右下的节点。如果是后者，我们希望遍历完这个前驱节点之后再回到当前节点，可以将它的 right 指针指向当前节点。
//
//Morris 中序遍历的一个重要步骤就是寻找当前节点的前驱节点，并且 Morris 中序遍历寻找下一个点始终是通过转移到 right 指针指向的位置来完成的。
//
//如果当前节点没有左子树，则遍历这个点，然后跳转到当前节点的右子树。
//如果当前节点有左子树，那么它的前驱节点一定在左子树上，我们可以在左子树上一直向右行走，找到当前点的前驱节点。
//如果前驱节点没有右子树，就将前驱节点的 right 指针指向当前节点。这一步是为了在遍历完前驱节点后能找到前驱节点的后继，也就是当前节点。
//如果前驱节点的右子树为当前节点，说明前驱节点已经被遍历过并被修改了 right 指针，这个时候我们重新将前驱的右孩子设置为空，遍历当前的点，然后跳转到当前节点的右子树。
//时间复杂度：O(n)。每个点被访问的次数不会超过两次，故这里的时间复杂度是 O(n)O(n)。
//空间复杂度：O(1)。使用临时空间的大小和输入规模无关。

func FindModeInMorris(root *Node) (answer []int) {
	var base, count, maxCount int
	update := func(x int) {
		if x == base {
			count++
		} else {
			base, count = x, 1
		}
		if count == maxCount {
			answer = append(answer, base) //累加
		} else if count > maxCount {
			maxCount = count
			answer = []int{base} //更新最大的众数
		}
	}

	cur := root
	for cur != nil {
		if cur.Left == nil { //如果没有左子树
			update(cur.Val) //遍历这个点
			cur = cur.Right //跳转到右子树
			continue
		}
		pre := cur.Left //如果当前节点有左子树，那么它的前驱节点一定在左子树上
		//在左子树上一直向右行走，找到当前节点的前驱节点
		for pre.Right != nil && pre.Right != cur {
			pre = pre.Right
		}
		//如果前驱节点没有右子树，就将前驱节点的 right 指针指向当前节点
		if pre.Right == nil {
			pre.Right = cur
			//遍历完前驱节点后能找到前驱节点的后继，也就是当前节点。
			cur = cur.Left
		} else {
			//如果前驱节点的右子树为当前节点，说明前驱节点已经被遍历过并被修改了 right 指针
			//我们重新将前驱的右孩子设置为空
			pre.Right = nil
			//遍历当前节点点，然后跳转到当前节点的右子树
			update(cur.Val)
			cur = cur.Right
		}
	}
	return
}
